package main

import (
	"fmt"
)

/**
执行用时：4 ms, 在所有 Go 提交中击败了30.47%的用户
内存消耗：2.7 MB, 在所有 Go 提交中击败了60.10%的用户
 */
func searchMatrix(matrix [][]int, target int) bool {

	n, m := len(matrix), len(matrix[0])
	l, r := 0, n * m - 1
	for l < r {
		mid := (l + r) >> 1
		if matrix[mid / m][mid % m] >= target {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return matrix[l / m][l % m] == target
}

func main() {

	matrix := [][]int{
		{1, 3, 5, 7},
		{10, 11, 16, 20},
		{23, 30, 34, 60},
	}
	fmt.Println(searchMatrix(matrix, 3))  // true
	fmt.Println(searchMatrix(matrix, 13))  // false
}
